package airthmetic.exercise.linkedList;


import java.awt.*;
import java.util.ArrayList;

/**
 * @author Douhy
 * @Date 2021/12/22
 * @Description 链表相关算法练习
 */
public class LinkedListDemo {

    //反转链表 递归
    public static ListNode reverseListForRecursion(ListNode head) {

        return null;
    }

    /**
     * 反转链表 - 迭代
     *
     * @param head
     * @return airthmetic.exercise.linkedList.ListNode
     * @author Douhy
     * @date 2021/12/22
     */
    public static ListNode reverseListForIteration(ListNode head) {
        // 思路 拿到下一个元素和保留前一个元素  循环赋值
   /*  *//*
        ListNode prev = null, next;
        ListNode current = head;
        while (current != null){
            // 拿到下一个元素 指向临时变量 next = 2
            next = current.next;
            current.next = prev;
             prev = current;
            current = next;
        }
        return prev;
        *//*

        // 优化版
        // 反转后的链表
        ListNode newHead = null;
        // 下一个元素临时变量 (两个作用：
        //                          1.这里为了保留内存地址指向,否则可能会被gc回收
        //                          2.下一个元素需要再循环末尾覆盖掉循环对象 形成循环)
        ListNode temp;
        while (head != null) {
            // 1.拿到下一个元素
            temp = head.next;
            // 2.head的next指向newHead(第一次是null，之后newHead被赋值为上次循环的head[第3步])
            head.next = newHead;
            // 3. 当前执行逻辑head赋值给上一个head
            newHead = head;
            // 当前元素指向 下一个元素(下一个元素赋值到循环对象)
            head = temp;
        }
        return newHead;*/


        ListNode current = head;
        ListNode prev = null;
        ListNode next = null;

        while (current != null){
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }

        return prev;

    }

    // Leetcode 237:删除链表中的节点 (难点： 没有头节点信息)
    public static void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }


    // Leetcode 141:环形链表
    //    给你一个链表的头节点 head ，判断链表中是否有环。
    //
    //    如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
    //
    //    如果链表中存在环 ，则返回 true 。 否则，返回 false 。
    public static boolean checkListNodeHasCycle(ListNode head) {
//        // 思路 快慢指针 快指针每次next两次 慢指针每次next一次 (快指针每次靠近慢指针一个next)
//        if (head == null || head.next == null) {
//            return false;
//        }
//
//        ListNode fastNode = head.next;
//        ListNode slowNode = head;
//        while (fastNode != null && fastNode.next != null) {
//            fastNode = fastNode.next.next;
//            slowNode = slowNode.next;
//
//            if (fastNode == slowNode) return true;
//        }
//
//        return false;










        if (head == null || head.next == null) {
            return false;
        }

        ListNode fastNode = head;
        ListNode slowNode = head;

        while (fastNode != null && fastNode.next != null){
            fastNode = fastNode.next.next;
            slowNode = slowNode.next;

            if (fastNode == slowNode){
                return true;
            }
        }
        return false;














    }

    // leetCode 203.移除链表元素
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        head.next = removeElements(head.next, val);
        if (head.val == val) {
            return head.next;
        }
        return head;
    }

    // leetCode 203.移除链表元素 (虚拟节点  遍历 指针做法)
    public static ListNode removeElements02(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        ListNode newHead = new ListNode(0);
        ListNode newLast = newHead;
        while (head != null) {
            if (head.val != val) {
                newLast.next = head;
                System.out.println("head :" + head);
                System.out.println("newHead :" + newHead);
                System.out.println("newLast :" + newLast);
                newLast = head;
                System.out.println("head :" + head);
                System.out.println("newHead :" + newHead);
                System.out.println("newLast :" + newLast);
                System.out.println("==============================================================");
//                newLast = newLast.next = head;

            }
            head = head.next;
        }
        newLast.next = null;
        return newHead.next;


//
//
//
//
//
//
//
//
//        ListNode newHead = new ListNode(0);
//        ListNode newLast = newHead;
//        while (head != null){
//            if (head.val != val){
//                newLast.next = head;
//                newLast = head;
//            }
//            head = head.next;
//        }
//
//        // 最后一个 node 需要清空
//        newLast.next = null;
//        return newHead.next;
    }


    // leetCode 83. 删除排序链表中的重复元素
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        head.next = deleteDuplicates(head.next);
        if (head.val == head.next.val) head = head.next;
        return head;

    }

    // leetCode 876. 链表的中间结点
    public static ListNode middleNode(ListNode head) {
        // 自实现方式
//        if(head.next == null) return head;
//
//        ListNode returnHead = head;
//        int num = 0;
//        while(head != null){
//            head = head.next;
//            num++;
//        }
//
//        int returnHeadNum = (int)(num >> 1) + 1;
//
//        for (int i = 1; i < returnHeadNum ; i++) {
//            returnHead = returnHead.next;
//        }
//        return returnHead;

        // 快慢指针方式
        if (head.next == null) return head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            head = head.next;
        }
        return head;
    }


    // leetCode 21. 合并两个有序链表(递归写法)
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode res = l1.val < l2.val ? l1 : l2;
        res.next = mergeTwoLists(res.next, l1.val >= l2.val ? l1 : l2);
        return res;
    }

    // leetCode 面试题02.07  leetCode 面试题52
    // leetCode 160. 相交链表
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode varA = headA;
        ListNode varB = headB;

        while (varA != varB) { //
            // 进来了说明 （A != B) 各自next = current    当为null后拼对立的链表(让长度统一  A+B=B+A) 长度统一之后找相等的第一个位置
            // 如果没有相等，A拼接B 与 B拼接A 长度一致 都会到达临界点(A+B 或 B+A的 最后一个node A和B再次next时都会返回null)
            // 此时打破循环条件(varA != varB) 返回varA或者valB都可以
            varA = (varA == null) ? headB : varA.next;
            varB = (varB == null) ? headA : varB.next;
        }

        return varA;
    }

    // leetCode 2. 两数相加
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 边界返回
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        // 虚拟头节点
        ListNode dummyHead = new ListNode(0);
        ListNode newLast = dummyHead;

        int carry = 0;
        // 链表可能不一样长 循环结束条件应该是任两条链表都为空结束
        while (l1 != null || l2 != null) {
            int l1Val = (l1 != null ? l1.val : 0);
            int l2Val = (l2 != null ? l2.val : 0);

            int tempNodeVal = (l1Val + l2Val + carry) % 10;
            ListNode tempNode = new ListNode(tempNodeVal);
            newLast.next = tempNode;
            newLast = tempNode;
            carry = (l1Val + l2Val + carry) / 10;

            // 循环
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }

        if (carry > 0) {
            newLast.next = new ListNode(carry);
        }
        return dummyHead.next;
    }

    // leetCode 86. 分隔链表
    public static ListNode partition(ListNode head, int x) {
        if (head == null) return null;
        ListNode lHead = new ListNode(0);
        ListNode lLast = lHead;
        ListNode rHead = new ListNode(0);
        ListNode rLast = rHead;
        while (head != null) {
            if (head.val < x) {
                lLast.next = head;
                lLast = head;
            } else {
                rLast.next = head;
                rLast = head;
            }
            head = head.next;
        }
        rLast.next = null;
        lLast.next = rHead.next;

        return lHead.next;
    }


    public static void main(String[] args) {
        // 反转链表
        ListNode listNode6 = new ListNode(6, null);
        ListNode listNode5 = new ListNode(5, listNode6);
        ListNode listNode4 = new ListNode(4, listNode5);

        ListNode listNode3 = new ListNode(3, listNode4);
        ListNode listNode2 = new ListNode(2, listNode3);
        ListNode listNode = new ListNode(1, listNode2);


        System.out.println("反转前："+ listNode);
        ListNode returnListNode = reverseListForIteration(listNode);
        System.out.println("反转后："+ returnListNode);


        // middleNode
//        ListNode listNode4 = new ListNode(4, null);
//        ListNode listNode3 = new ListNode(3, null);
//        ListNode listNode2 = new ListNode(2, listNode3);
//        ListNode listNode = new ListNode(1, listNode2);
//        System.out.println(middleNode(listNode));

//        System.out.println(mergeTwoLists(listNode4, listNode));
//        System.out.println(removeElements02(listNode, 6));

        // 两数相加
//        System.out.println(addTwoNumbers(listNode, listNode4));

        // 分隔链表
//        System.out.println(partition(listNode, 5));
    }
}



